/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:全O1的数据结构.java
 * Date:2021/02/18 14:22:18
 */

package org.bytedance.数据结构;

import com.alibaba.fastjson.JSONObject;

import java.util.HashMap;
import java.util.Map;

/**
 * 请你实现一个数据结构支持以下操作：
 * <p>
 * Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
 * Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否则使一个存在的 key 值减一。
 * 如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
 * GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串"" 。
 * GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。
 */
public class 全O1的数据结构 {

    public static void main(String[] args) {
        全O1的数据结构 instance = new 全O1的数据结构();
        instance.inc("hello");
        instance.inc("world");
        instance.inc("hello");
        instance.inc("hello");
        instance.inc("he");
        instance.inc("world");
        instance.dec("he");
        System.out.println(JSONObject.toJSONString(instance.map));
        String maxKey = instance.getMaxKey();
        System.out.println(maxKey);
        String minKey = instance.getMinKey();
        System.out.println(minKey);
    }

    private Map<String, Node> map;

    private Node head, tail;

    class Node {
        int value;
        String key;
        Node pre;
        Node next;

        public Node(String key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * Initialize your data structure here.
     */
    public 全O1的数据结构() {
        map = new HashMap<>();
        head = new Node("", -1);
        tail = new Node("", -1);
        head.next = tail;
        tail.pre = head;
    }

    //将node1插入到node2的前面
    //  tmp<-node2
    public void insertPre(Node node1, Node node2) {
        Node tmp = node2.pre;
        node1.next = node2;
        node2.pre = node1;
        tmp.next = node1;
        node1.pre = tmp;
    }

    //将node1插入到node2的后面
    // node2 <-> tmp
    public void insertPost(Node node1, Node node2) {
        Node tmp = node2.next;
        tmp.pre = node1;
        node1.next = tmp;
        node2.next = node1;
        node1.pre = node2;
    }

    /**
     * Inserts a new key <Key> with value 1. Or increments an existing key by 1.
     */
    public void inc(String key) {
        if (null == key || key.isEmpty()) return;
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value++;
            //找到大于等于它的第一个node，插入到前面
            if (node.next != tail) {
                Node tmp = node.next;
                while (tmp != tail && tmp.value < node.value) {
                    tmp = tmp.next;
                }
                node.pre.next = node.next;
                node.next.pre = node.pre;
                insertPre(node, tmp);
            }
        } else {
            Node node = new Node(key, 1);
            map.put(key, node);
            insertPost(node, head);
        }

    }

    /**
     * Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
     */
    public void dec(String key) {
        if (key == null || key.isEmpty()) return;
        if (map.containsKey(key)) {
            Node node = map.get(key);
            if (node.value == 1) {
                node.pre.next = node.next;
                node.next.pre = node.pre;
                map.remove(key);
            } else {
                node.value--;
                if (node.pre != head) {
                    Node tmp = node.pre;
                    while (tmp != head && tmp.value > node.value) {
                        tmp = tmp.pre;
                    }
                    //断开连接
                    node.pre.next = node.next;
                    node.next.pre = node.pre;
                    insertPost(node, tmp);
                }
            }
        } else {
            return;
        }

    }

    /**
     * Returns one of the keys with maximal value.
     */
    public String getMaxKey() {
        return tail.pre.key;
    }

    /**
     * Returns one of the keys with Minimal value.
     */
    public String getMinKey() {
        return head.next.key;
    }

}
